package algorithm;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author MaGuangQi
 * @description:https://leetcode-cn.com/problems/valid-anagram/
 * 242题 给2个字符串, 判断是否是异位词。
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 *
 * 输入: s = "rat", t = "car"
 * 输出: false
 * @date 2020-06-19 23:22
 **/
public class Anagram {
    /**
    *解法1: 使用排序,把2个字母的值排序,最后比较2个是否相等
     * 时间复杂度O(N)*O(logN) 因为要排序,快排时间复杂度O(logN)
    */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        List<Character> a = new ArrayList<>(s.length());
        List<Character> b = new ArrayList<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            char c1 = t.charAt(i);
            a.add(c);
            b.add(c1);
        }
        Collections.sort(a);
        Collections.sort(b);
        return a.equals(b);
    }
    /**
    *解法二: 使用hash表, 将每个字符串中的字母计数.
     * 最后比较2个hash表是否一样
     * 时间复杂度O(N)*O(1) O(1)是因为hash表插入操作是O(1)
    */
    public boolean isAnagram2(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            int j=0;
            char c = s.charAt(i);
            if (map1.get(c) == null) {
                j++;
                map1.put(c, j);
            } else {
                map1.put(c, map1.get(c)+1);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            int j=0;
            char c = t.charAt(i);
            if (map2.get(c) == null) {
                j++;
                map2.put(c, j);
            } else {
                map2.put(c, map2.get(c)+1);
            }
        }
        return map1.equals(map2);
    }
    //------------------------------优化后
    /**
    *解法一优化
    */
    public boolean isAnagram3(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }
    /**
     *解法二优化
     * 为了检验t是否是s的重新排序,因为题目说是26个小写字母,因此我们可以使用
     * 一个26个简单的计数器
     * 注意:不需要2个计数器,只需要一个计算器,s负责加,t负责减,最后判断数组元素是否都是0
     * 本质是一种hash表
     *时间复杂度：O(n)O(n)。时间复杂度为 O(n)O(n) 因为访问计数器表是一个固定的时间操作
     * 空间复杂度：O(1)O(1)。尽管我们使用了额外的空间，但是空间的复杂性是 O(1)O(1)，因为无论 NN 有多大，表的大小都保持不变。
     */
    public boolean isAnagram4(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] counter = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counter[s.charAt(i)-'a']++;
            counter[t.charAt(i)-'a']--;
        }
        for (int count : counter) {
            if (count != 0) {
                return false;
            }

        }
        return true;
    }

    public static void main(String[] args) {
        Anagram anagram = new Anagram();
        System.out.println(anagram.isAnagram2("tar", "rat"));
        System.out.println(anagram.isAnagram2("tar", "raa"));
    }
}
